% 所有DCU-CPU异构计算的伪代码模板，请手动复制到main.tex中相应位置

\begin{algorithm}[H]
\caption{优化的CPU矩阵乘法实现}
\label{alg:cpu_optimized}
\begin{algorithmic}[1]
\Procedure{MatrixMultiplyOptimized}{$A, B, C$}
    \State $M \gets A.rows$
    \State $K \gets A.cols$
    \State $N \gets B.cols$
    \State $cblas\_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans,$ \Comment{调用OpenBLAS的SGEMM函数进行计算}
    \State $              M, N, K,$
    \State $              1.0, A.data, K,$
    \State $                   B.data, N,$
    \State $              0.0, C.data, N)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{DCU内存池管理机制}
\label{alg:dcu_memory_pool}
\begin{algorithmic}[1]
\Procedure{DCUMemoryPool::allocate}{$size$}
    \State \Comment{查找是否有可重用的缓冲区}
    \If{存在大小为$size$的空闲内存块}
        \State 返回该内存块并从空闲列表移除
    \Else
        \State 分配新的设备内存
        \State 返回新分配的内存指针
    \EndIf
\EndProcedure

\Procedure{DCUMemoryPool::release}{$ptr, size$}
    \State \Comment{将内存返回池中而非释放}
    \If{池中该大小的内存块数量 < 阈值}
        \State 将$ptr$添加到对应大小的空闲列表
    \Else
        \State 直接释放内存
    \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{基于共享内存的DCU矩阵乘法}
\label{alg:dcu_shared}
\begin{algorithmic}[1]
\Procedure{SharedMemoryKernel}{$A, B, C, M, N, K$}
    \State shared float subA[BLOCK\_SIZE][BLOCK\_SIZE] \Comment{在共享内存中分配缓冲区}
    \State shared float subB[BLOCK\_SIZE][BLOCK\_SIZE]
    
    \State 计算当前线程负责的行和列索引
    
    \State sum = 0.0
    \For{每个BLOCK\_SIZE大小的A和B子矩阵}
        \State 将A和B的子矩阵加载到共享内存
        \State 线程同步(\_\_syncthreads())
        
        \For{k = 0 to BLOCK\_SIZE-1}
            \State sum += subA[threadRow][k] * subB[k][threadCol]
        \EndFor
        
        \State 线程同步(\_\_syncthreads())
    \EndFor
    
    \State C[row][col] = sum
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{DCU算法自适应选择策略}
\label{alg:dcu_adaptive}
\begin{algorithmic}[1]
\Procedure{SelectOptimalDCUAlgorithm}{$M, K, N$}
    \State matrixSize = $M \times K \times N$
    \State isLargeMatrix = ($M \geq 4096$ AND $N \geq 4096$ AND $K \geq 4096$)
    \State isPotentiallyMedium = ($M \geq 1024$ OR $N \geq 1024$ OR $K \geq 1024$)
    \State useSharedCandidate = ($M \leq 512$ AND $N \leq 512$ AND $K \leq 512$)
    \State isGenerallySmall = (matrixSize < 1000000)
    
    \If{isLargeMatrix}
        \State \Return multiplyLargeMatrix  \Comment{大矩阵使用分块多流算法}
    \ElsIf{useSharedCandidate}
        \State \Return multiplyShared  \Comment{小矩阵使用共享内存优化}
    \ElsIf{isPotentiallyMedium}
        \State \Return multiplyPipelined  \Comment{中等矩阵使用流水线优化}
    \ElsIf{isGenerallySmall}
        \State \Return multiplyShared  \Comment{小矩阵使用共享内存优化}
    \Else
        \State \Return multiplyHipBLAS  \Comment{其他情况使用hipBLAS}
    \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{混合模式任务划分策略}
\label{alg:hybrid_task_division}
\begin{algorithmic}[1]
\Procedure{DivideTask}{$A, B, cpuRatio, M, K, N$}
    \State cpuRows = $M \times cpuRatio$ \Comment{根据比例计算CPU和DCU处理的行数}
    \State dcuRows = $M - cpuRows$
    
    \State A\_cpu = A的前cpuRows行 \Comment{划分矩阵A}
    \State A\_dcu = A的后dcuRows行
    
    \State \Comment{矩阵B不需要划分，完整传递给两个设备}
    
    \State C\_cpu = 新矩阵(cpuRows, N) \Comment{为结果矩阵分配空间}
    \State C\_dcu = 新矩阵(dcuRows, N)
    
    \State \Return A\_cpu, A\_dcu, B, C\_cpu, C\_dcu
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{动态负载均衡机制}
\label{alg:dynamic_load_balancing}
\begin{algorithmic}[1]
\Procedure{ComputeOptimalRatio}{$M, N, K$}
    \State total\_elements = $M \times K + K \times N + M \times N$
    \State small\_threshold = $512 \times 512 \times 3$
    \State large\_threshold = $2048 \times 2048 \times 3$
    
    \If{$M \leq 64$}  \Comment{非常小的行数}
        \State cpuRatio = 0.95
    \ElsIf{total\_elements <= small\_threshold}
        \State cpuRatio = 0.30  \Comment{小矩阵分配较多给CPU}
    \ElsIf{total\_elements >= large\_threshold}
        \State cpuRatio = 0.01  \Comment{大矩阵主要分配给DCU}
    \Else
        \State cpuRatio = 0.10  \Comment{中等矩阵的默认分配}
    \EndIf
    
    \State \Comment{确保分配合理的最小计算块}
    \State min\_chunk\_size = 32
    \If{$M > min\_chunk\_size \times 2$}
        \If{cpuRows == 0} cpuRows = min\_chunk\_size \EndIf
        \If{cpuRows > $M - min\_chunk\_size$} cpuRows = $M - min\_chunk\_size$ \EndIf
    \EndIf
    
    \State \Return cpuRatio
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{异步执行机制}
\label{alg:async_execution}
\begin{algorithmic}[1]
\Procedure{ExecuteHybridMode}{$A, B, C, cpuRatio, M, K, N$}
    \State A\_cpu, A\_dcu, B, C\_cpu, C\_dcu = DivideTask(A, B, cpuRatio, M, K, N) \Comment{划分任务}
    
    \State cpuFuture = async\_launch(\{ \Comment{异步启动CPU计算任务}
        \State \quad matrixMultiplyOptimized(A\_cpu, B, C\_cpu)
    \State \})
    
    \State dcuMatrixMultiply(A\_dcu, B, C\_dcu) \Comment{主线程执行DCU计算}
    
    \State cpuFuture.wait() \Comment{等待CPU任务完成}
    
    \State MergeResults(C, C\_cpu, C\_dcu) \Comment{合并结果}
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{自适应迭代测试机制}
\label{alg:adaptive_iterations}
\begin{algorithmic}[1]
\Procedure{AdaptiveTest}{$M, K, N, iterations$}
    \State initial\_cpu\_ratio = 0.5
    \State best\_hybrid\_time = $\infty$
    \State best\_cpu\_ratio = -1
    
    \For{iter = 1 to iterations}
        \State cpu\_time = MeasurePerformance(CPU\_MODE, M, K, N) \Comment{测量纯CPU模式性能}
        
        \State dcu\_time = MeasurePerformance(DCU\_MODE, M, K, N) \Comment{测量纯DCU模式性能}
        
        \If{iter > 1}
            \State cpu\_ratio = dcu\_time / (cpu\_time + dcu\_time) \Comment{基于历史性能调整CPU比例}
            \State cpu\_ratio = Clamp(cpu\_ratio, 0.0, 1.0)
        \Else
            \State cpu\_ratio = initial\_cpu\_ratio
        \EndIf
        
        \State hybrid\_time = MeasurePerformance(HYBRID\_MODE, M, K, N, cpu\_ratio) \Comment{使用当前比例测试混合模式}
        
        \If{hybrid\_time < best\_hybrid\_time}
            \State best\_hybrid\_time = hybrid\_time
            \State best\_cpu\_ratio = cpu\_ratio
        \EndIf
    \EndFor
    
    \State \Return best\_hybrid\_time, best\_cpu\_ratio
\EndProcedure
\end{algorithmic}
\end{algorithm} 